package com.springchang.leetcode.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 *  leetcode 70号题目：爬楼梯
 */
public class ClimbingStairs_70 {

    //解法1.用map记录已经求到过的值，否则时间绝对回超时
    Map<Integer, Integer> map = new HashMap<>();

    //递归方式解题方式
    public int climbStairsWithRecursive(int n) {
        if(n == 0) {
            return 1;
        } else if(n == 1) {
            return 1;
        } else {
            if(map.get(n) != null) {
                return map.get(n);
            } else {
                int result = climbStairsWithRecursive(n-1) + climbStairsWithRecursive(n-2);
                map.put(n ,result);
                return result;
            }
        }
    }

    //非递归方式解题方式
    public int climbStairsWithoutRecursive(int n) {

        if(n == 1) return 1;

        int result = 0;
        int prev = 1;
        int preprev = 1;

        for (int i = 2; i <= n; i++) {
            result = prev + preprev;

            preprev = prev;
            prev = result;
        }
        return result;
    }

    public static void main(String[] args) {
        ClimbingStairs_70 climbingStairs = new ClimbingStairs_70();
        System.out.println(String.format("递归方式结算结果   : %s", climbingStairs.climbStairsWithRecursive(1)));
        System.out.println(String.format("非递归方式计算结果  : %s", climbingStairs.climbStairsWithoutRecursive(1)));
    }
}
